\chapter{Conclusion} % Main chapter title

\label{Chapter7} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 7. \emph{Conclusion}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

%%----------------------------------------------------------------------------------------
%%	SECTION 1
%%----------------------------------------------------------------------------------------
%\section{Main Section 1}
%
%%-----------------------------------
%%	SUBSECTION 1
%%-----------------------------------
%\subsection{Subsection 1}
%%-----------------------------------
%%	SUBSECTION 2
%%-----------------------------------
%\subsection{Subsection 2}

Dans ce travail, nous avons étudié la propagation et les techniques de consistance fortes existantes. Pour les CSPs binaires (dont les contraintes sont binaires), nous avons les consistances RPC, PIC, MaxRPC, SAC, NIC. Pour les CSPs non-binaire, les consistances RPC, PIC, MaxRPC, NIC sont étendu à RPWC, rPIC, MaxRPWC, rNIC. La puissant d'élagage de ces consistances est également étudié. Entre les consistances pour les contraintes non-binaires, MaxRPWC est plus fort que rPIC, rPIC est plus fort que RPWC, et RPWC est plus fort que GAC. Les algorithmes pour RPWC, rPIC et MaxRPWC sont étudiés dans ce mémoire. Parmi lesquels, l'algorithme MaxRPWC3 est le plus intéressant pour sa puissance d'élagage et sa complexité de temps.

Pour la partie pratique, nous avons d'abord étudié le solveur AbsCon. Sur ce solveur, quelques algorithmes de propagation sont déjà implémentés tels que GAC (STR2), SAC, PWC+GAC. Ensuite, nous avons implémenté les algorithmes RPWC1, rPIC1, MaxRPWC1, MaxRPWC3 dans ce solveur. Nous avons expérimenté ces algorithmes pour analyser l'avantage d'utilisation des consistances fortes. Le résultat pratique montre que les consistances fortes permet de réduire l'espace de recherche. Dans certain cas, l'algorithme pour ces consistances fortes marche plus rapide que l'algorithme pour GAC. Par contre, la complexité de ces algorithmes est assez grande, dans le cas qu'ils ne peuvent pas réduire assez l'espace de recherche, ils résolvent plus lent que GAC. Parmi les algorithmes implémentés dans ce travail, MaxRPWC3 est prometteur. L'algorithme PWC+GAC marche plus rapide entre les algorithmes de consistances fortes.

Pour perspectives, nous proposons d'améliorer l'algorithme MaxRPWC3. Il faut d'abord améliorer l'implémentation de cette algorithme. La partie \textit{backtracking} pour le pointeur $lastPW_{x_j,a,c_i,c_m}$ est coûteuse. Puis, il faut trouver une façon efficace pour le teste d'extensibilité des tuples (GAC-support). 
La consistance \textit{Max Restricted k-wise Consistency (MaxRkWC)} (génération de MaxRPWC) serait considérée. La génération de la consistance PWC+GAC serait également considérée. L'autre notion de consistance serait examinée et proposée. L'étape suivant est d'envisager la combinaison de ces consistances.

%Pour perspectives, continuer sur MaxRPWC: améliorer, examiner, PWC + GAC : continuer sur cette algorithme? 
%Il s'agit d'améliorer l'implémentation de cet algorithme dans la partie de \textit{backtracking}. Le coût de backtracking pour le pointeur $lastPW_{x_j,a,c_i,c_m}$ est peut-être cher.
